package sword_offer;

public class _47MaxLiftValue {
    public static void main(String[] args) {

    }
    public int maxValue(int[][] grid) {
        // 创建一维数组，存储各个位置最大礼物值
        int[] array = new int[grid[0].length];
        // 初始化数组
        array[0] = grid[0][0];
        for (int i = 1; i < grid[0].length; i++) {
            array[i] = grid[0][i] + array[i - 1];
        }

        // 遍历一次二维数组
        for (int i = 1; i < grid.length; i++) {
            array[0] = array[0] + grid[i][0];
            for (int j = 1; j < grid[i].length; j++) {
                array[j] = array[j - 1] > array[j]? array[j - 1] + grid[i][j] : array[j] + grid[i][j];
            }
        }

        return array[array.length - 1];
    }
}
